package com.jia.leetCode;

import com.jia.leetCode.Pro0143.ListNode;

public class Pro0019 {
	//双指针
	public ListNode removeNthFromEnd(ListNode head, int n) {
		int i = 0;
		ListNode cur = head;
		while(cur!= null && i < n) {++i; cur = cur.next;}
		if(i < n) return head; //链表长度小于n
		if(cur == null) return head.next; //刚好链表长度和n相同，删除头结点
		ListNode pre = head; //pre删除倒数n的节点的前一个节点
		while(cur!=null && cur.next != null) {
			cur = cur.next;
			pre = pre.next;
		}
		pre.next = pre.next.next;//删除pre的下一个节点
		return head;
	}
	 public ListNode removeNthFromEnd2(ListNode head, int n) {
	        ListNode fast = head;
	        while(n-->0) {
	            fast = fast.next;
	        }
	        if(fast == null) return head.next;
	        ListNode slow = head;
	        while(fast.next != null) {
	            fast = fast.next;
	            slow = slow.next;
	        }
	        slow.next = slow.next.next;
	        return head;
	    }
}
